Total suppression of a large spin tunneling barrier in quantum adiabatic computation

摘要

We apply a quantum adiabatic evolution algorithm to a combinatorialoptimization problem where the cost function depends entirely on the of thenumber of unit bits in a n-bit string (Hamming weight). The solution of theoptimization problem is encoded as a ground state of the problem HamiltonianH_p for the z-projection of a total spin-n/2. We show that tunneling barriersfor the total spin can be completely suppressed during the algorithm if theinitial Hamiltonian has its ground state extended in the space of thez-projections of the spin. This suppression takes place even if the costfunction has deep and well separated local minima. We provide an intuitivepicture for this effect and show that it guarantees the polynomial complexityof the algorithm in a very broad class of cost functions. We suggest a simpleexample of the Hamiltonian for the adiabatic evolution: H(tau) = (1-tau) hatS_{x}^{2} + tau H_p, with parameter tau slowly varying in time between 0 and 1.We use WKB analysis for the large spin to estimate the minimum energy gapbetween the two lowest adiabatic eigenvalues of H(tau).